/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.tree

import junit.framework.TestCase.assertEquals
import org.jheaps.AddressableHeap
import org.junit.Assert
import org.junit.BeforeClass
import org.junit.Test
import java.io.*
import java.util.*

abstract class AbstractAddressableHeapTest {
     class TestComparator : Comparator<Int?>, Serializable {
        override fun compare(o1: Int?, o2: Int?): Int {
            return if (o1!! < o2!!) {
                1
            } else if (o1 > o2) {
                -1
            } else {
                0
            }
        }
    }

    protected abstract fun createHeap(): AddressableHeap<Int, Void>

    protected abstract fun createHeap(comparator: Comparator<Int?>?): AddressableHeap<Int, Void>

    protected abstract fun createHeapWithStringValues(): AddressableHeap<Int, String>

    @Test
    open fun test() {
        val h = createHeap()

        for (i in 0 until SIZE) {
            h.insert(i)
            assertEquals(0, h.findMin().key)
            Assert.assertFalse(h.isEmpty)
            Assert.assertEquals(h.size(), (i + 1).toLong())
        }

        for (i in SIZE - 1 downTo 0) {
            assertEquals(h.findMin().key, SIZE - i - 1)
            h.deleteMin()
        }
    }

    @Test
    open fun testOnlyInsert() {
        val h = createHeap()

        for (i in 0 until SIZE) {
            h.insert(SIZE - i)
            assertEquals(SIZE - i, h.findMin().key)
            Assert.assertFalse(h.isEmpty)
            Assert.assertEquals(h.size(), (i + 1).toLong())
        }
    }

    @Test
    fun testSetValue() {
        val h = createHeapWithStringValues()
        h.insert(1, "value1").value = "value2"
        assertEquals("value2", h.findMin().value)
    }

    @Test
    open fun testOnly4() {
        val h = createHeap()

        Assert.assertTrue(h.isEmpty)

        h.insert(780)
        Assert.assertEquals(h.size(), 1)
        assertEquals(780, h.findMin().key)

        h.insert(-389)
        Assert.assertEquals(h.size(), 2)
        assertEquals(-389, h.findMin().key)

        h.insert(306)
        Assert.assertEquals(h.size(), 3)
        assertEquals(-389, h.findMin().key)

        h.insert(579)
        Assert.assertEquals(h.size(), 4)
        assertEquals(-389, h.findMin().key)

        h.deleteMin()
        Assert.assertEquals(h.size(), 3)
        assertEquals(306, h.findMin().key)

        h.deleteMin()
        Assert.assertEquals(h.size(), 2)
        assertEquals(579, h.findMin().key)

        h.deleteMin()
        Assert.assertEquals(h.size(), 1)
        assertEquals(780, h.findMin().key)

        h.deleteMin()
        Assert.assertEquals(h.size(), 0)

        Assert.assertTrue(h.isEmpty)
    }

    @Test
    open fun testOnly4Reverse() {
        val h = createHeap(comparator)

        Assert.assertTrue(h.isEmpty)

        h.insert(780)
        Assert.assertEquals(h.size(), 1)
        assertEquals(780, h.findMin().key)

        h.insert(-389)
        Assert.assertEquals(h.size(), 2)
        assertEquals(780, h.findMin().key)

        h.insert(306)
        Assert.assertEquals(h.size(), 3)
        assertEquals(780, h.findMin().key)

        h.insert(579)
        Assert.assertEquals(h.size(), 4)
        assertEquals(780, h.findMin().key)

        h.deleteMin()
        Assert.assertEquals(h.size(), 3)
        assertEquals(579, h.findMin().key)

        h.deleteMin()
        Assert.assertEquals(h.size(), 2)
        assertEquals(306, h.findMin().key)

        h.deleteMin()
        Assert.assertEquals(h.size(), 1)
        assertEquals(-389, h.findMin().key)

        h.deleteMin()
        Assert.assertEquals(h.size(), 0)

        Assert.assertTrue(h.isEmpty)
    }

    @Test
    fun testSortRandomSeed1() {
        val h = createHeap()

        val generator = Random(1)

        for (i in 0 until SIZE) {
            h.insert(generator.nextInt())
        }

        var prev: Int? = null
        var cur: Int?
        while (!h.isEmpty) {
            cur = h.findMin().key
            h.deleteMin()
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testSort1RandomSeed1() {
        val h = createHeap()

        val generator = Random(1)

        for (i in 0 until SIZE) {
            h.insert(generator.nextInt())
        }

        var prev: Int? = null
        var cur: Int?
        while (!h.isEmpty) {
            cur = h.deleteMin().key
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testSortRandomSeed2() {
        val h = createHeap()

        val generator = Random(2)

        for (i in 0 until SIZE) {
            h.insert(generator.nextInt())
        }

        var prev: Int? = null
        var cur: Int?
        while (!h.isEmpty) {
            cur = h.findMin().key
            h.deleteMin()
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testSort2RandomSeed2() {
        val h = createHeap()

        val generator = Random(2)

        for (i in 0 until SIZE) {
            h.insert(generator.nextInt())
        }

        var prev: Int? = null
        var cur: Int?
        while (!h.isEmpty) {
            cur = h.deleteMin().key
            if (prev != null) {
                Assert.assertTrue(prev.compareTo(cur!!) <= 0)
            }
            prev = cur
        }
    }

    @Test
    fun testFindMinDeleteMinSameObject() {
        val h = createHeap()

        val generator = Random(1)

        for (i in 0 until SIZE) {
            h.insert(generator.nextInt())
        }

        while (!h.isEmpty) {
            Assert.assertEquals(h.findMin(), h.deleteMin())
        }
    }

    @Test
    open fun testDelete() {
        val h = createHeap()
        val array: Array<AddressableHeap.Handle<Int, Void>> = Array(15){h.insert(it)}
        /*for (i in 0..14) {
            array[i] = h.insert(i)
        }*/

        array[5].delete()
        assertEquals(0, h.findMin().key)
        array[7].delete()
        assertEquals(0, h.findMin().key)
        array[0].delete()
        assertEquals(1, h.findMin().key)
        array[2].delete()
        assertEquals(1, h.findMin().key)
        array[1].delete()
        assertEquals(3, h.findMin().key)
        array[3].delete()
        assertEquals(4, h.findMin().key)
        array[9].delete()
        assertEquals(4, h.findMin().key)
        array[4].delete()
        assertEquals(6, h.findMin().key)
        array[8].delete()
        assertEquals(6, h.findMin().key)
        array[11].delete()
        assertEquals(6, h.findMin().key)
        array[6].delete()
        assertEquals(10, h.findMin().key)
        array[12].delete()
        assertEquals(10, h.findMin().key)
        array[10].delete()
        assertEquals(13, h.findMin().key)
        array[13].delete()
        assertEquals(14, h.findMin().key)
        array[14].delete()
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    open fun testDelete1() {
        val h = createHeap()

        /*val array: Array<AddressableHeap.Handle<Int?, Void>>
        array = arrayOfNulls<AddressableHeap.Handle<*, *>>(8)
        for (i in 0..7) {
            array[i] = h.insert(i)
        }*/

        val array = createArray1(SIZE,h)

        array[5].delete()
        assertEquals(0, h.findMin().key)
        array[7].delete()
        assertEquals(0, h.findMin().key)
        array[0].delete()
        assertEquals(1, h.findMin().key)
        array[2].delete()
        assertEquals(1, h.findMin().key)
        array[1].delete()
        assertEquals(3, h.findMin().key)
    }

    @Test
    open fun testAddDelete() {
        val h = createHeap()

        /*val array: Array<AddressableHeap.Handle<Int?, Void>>
        array = arrayOfNulls<AddressableHeap.Handle<*, *>>(SIZE)
        for (i in 0 until SIZE) {
            array[i] = h.insert(i)
        }*/
        val array: Array<AddressableHeap.Handle<Int, Void>> = Array(SIZE){h.insert(it)}

        for (i in SIZE - 1 downTo 0) {
            array[i].delete()
            if (i > 0) {
                assertEquals(0, h.findMin().key)
            }
        }
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    open fun testAddDeleteComparator() {
        val h = createHeap(comparator)

        /*val array: Array<AddressableHeap.Handle<Int, Void>>
        array = arrayOfNulls<AddressableHeap.Handle<*, *>>(SIZE)
        for (i in 0 until SIZE) {
            array[i] = h.insert(i)
        }*/
        val array = createArray(SIZE,h)

        for (i in 0 until SIZE) {
            array[i].delete()
            if (i < SIZE - 1) {
                assertEquals(SIZE - 1, h.findMin().key)
            }
        }
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    open fun testAddDecreaseKeyDeleteMin() {
        val h = createHeap()

        /*val array: Array<AddressableHeap.Handle<Int?, Void>>
        array = arrayOfNulls<AddressableHeap.Handle<*, *>>(SIZE)
        for (i in 0 until SIZE) {
            array[i] = h.insert(i)
        }*/
        val array: Array<AddressableHeap.Handle<Int, Void>> = Array(SIZE){h.insert(it)}

        for (i in SIZE / 2 until SIZE / 2 + 10) {
            array[i].decreaseKey(i / 2)
        }

        array[0].delete()

        for (i in SIZE / 2 + 10 until SIZE / 2 + 20) {
            array[i].decreaseKey(0)
        }

        assertEquals(0, h.deleteMin().key)
    }

    private fun createArray(size:Int, h:AddressableHeap<Int, Void>,block:(Int)->Int={it}):Array<AddressableHeap.Handle<Int, Void>>{
        val array: Array<AddressableHeap.Handle<Int, Void>> = Array(size){h.insert(block(it))}
        return array
    }

    private fun createArray1(size:Int, h:AddressableHeap<Int, Void>,block:(Int)->Int={it}):Array<AddressableHeap.Handle<Int, Void>>{
        val array: Array<AddressableHeap.Handle<Int, Void>> = Array(size){h.insert(block(it))}
        return array
    }
    
    @Test
    open fun testAddDecreaseKeyDeleteMinComparator() {
        val h = createHeap(comparator)

        /*val array: Array<AddressableHeap.Handle<Int, Void>>
        array = arrayOfNulls<AddressableHeap.Handle<*, *>>(SIZE)
        for (i in 0 until SIZE) {
            array[i] = h.insert(i)
        }*/

        val array = createArray(SIZE,h)
        
        for (i in SIZE / 2 until SIZE / 2 + 10) {
            array[i].decreaseKey(SIZE - 1)
        }

        array[SIZE - 1].delete()

        for (i in SIZE / 2 + 10 until SIZE / 2 + 20) {
            array[i].decreaseKey(SIZE - 1)
        }

        assertEquals(SIZE - 1, h.deleteMin().key)
    }

    @Test
    fun testClear() {
        val h = createHeap()

        for (i in 0..14) {
            h.insert(i)
        }

        h.clear()
        Assert.assertEquals(0L, h.size())
        Assert.assertTrue(h.isEmpty)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testDeleteTwice() {
        val h = createHeap()

        /*val array: Array<AddressableHeap.Handle<Int?, Void>>
        array = arrayOfNulls<AddressableHeap.Handle<*, *>>(15)
        for (i in 0..14) {
            array[i] = h.insert(i)
        }*/

        val array = createArray1(15,h)
        
        array[5].delete()
        assertEquals(0, h.findMin().key)
        array[7].delete()
        assertEquals(0, h.findMin().key)
        array[0].delete()
        assertEquals(1, h.findMin().key)
        array[2].delete()
        assertEquals(1, h.findMin().key)
        array[1].delete()
        assertEquals(3, h.findMin().key)
        array[3].delete()
        assertEquals(4, h.findMin().key)
        array[9].delete()
        assertEquals(4, h.findMin().key)
        array[4].delete()
        assertEquals(6, h.findMin().key)

        // again
        array[2].delete()
    }

    @Test(expected = IllegalArgumentException::class)
    fun testDeleteMinDeleteTwice() {
        val h = createHeap()
        val e1 = h.insert(50)
        h.insert(100)
        h.deleteMin()
        e1.delete()
    }

    @Test(expected = IllegalArgumentException::class)
    fun testDeleteMinDeleteTwice1() {
        val h = createHeap()

        for (i in 100..199) {
            h.insert(i)
        }

        h.deleteMin().delete()
    }

    @Test(expected = IllegalArgumentException::class)
    fun testDeleteMinDecreaseKey() {
        val h = createHeap()

        for (i in 100..199) {
            h.insert(i)
        }
        h.deleteMin().decreaseKey(0)
    }

    @Test(expected = NoSuchElementException::class)
    fun testNoElementFindMin() {
        val h = createHeap()
        h.findMin()
    }

    @Test(expected = NoSuchElementException::class)
    fun testNoElementDeleteMin() {
        val h = createHeap()
        h.deleteMin()
    }

    /*@Test(expected = NullPointerException::class)
    fun testInsertNull() {
        val h = createHeap()
        h.insert(null, null)
    }*/

    @Test
    fun testDecreaseKey() {
        val h = createHeap()

        /*val array: Array<AddressableHeap.Handle<Int?, Void>>
        array = arrayOfNulls<AddressableHeap.Handle<*, *>>(15)
        for (i in 0..14) {
            array[i] = h.insert(i + 100)
        }*/

        val array = createArray1(15,h){it+100}

        assertEquals(100, h.findMin().key)
        array[5].decreaseKey(5)
        assertEquals(5, h.findMin().key)
        array[1].decreaseKey(50)
        assertEquals(5, h.findMin().key)
        array[1].decreaseKey(20)
        assertEquals(5, h.findMin().key)
        array[5].delete()
        assertEquals(20, h.findMin().key)
        array[10].decreaseKey(3)
        assertEquals(3, h.findMin().key)
        array[0].decreaseKey(0)
        assertEquals(0, h.findMin().key)
    }

    @Test
    fun testDecreaseKeyWithComparator1() {
        val h = createHeap(comparator)

        /*val array: Array<AddressableHeap.Handle<Int, Void>>
        array = arrayOfNulls<AddressableHeap.Handle<*, *>>(15)
        for (i in 0..14) {
            array[i] = h.insert(i)
        }*/

        val array = createArray(15,h)
        
        assertEquals(14, h.findMin().key)
        array[5].decreaseKey(205)
        assertEquals(205, h.findMin().key)
        array[1].decreaseKey(250)
        assertEquals(250, h.findMin().key)
        array[1].decreaseKey(300)
        assertEquals(300, h.findMin().key)
        array[5].delete()
        assertEquals(300, h.findMin().key)
        array[10].decreaseKey(403)
        assertEquals(403, h.findMin().key)
        array[0].decreaseKey(1000)
        assertEquals(1000, h.findMin().key)
    }

    @Test
    fun testDecreaseKey1() {
        val h = createHeap()

       /* val array: Array<AddressableHeap.Handle<Int?, Void>>
        array = arrayOfNulls<AddressableHeap.Handle<*, *>>(1000)
        for (i in 0..999) {
            array[i] = h.insert(2000 + i)
        }*/

        val array = createArray1(1000,h){2000+it}

        for (i in 999 downTo 0) {
            array[i].decreaseKey(array[i].key!! - 2000)
        }

        for (i in 0..999) {
            assertEquals(i, h.deleteMin().key)
        }
    }

    @Test
    fun testDecreaseKeyWithComparator() {
        val h = createHeap(comparator)

        /*val array: Array<AddressableHeap.Handle<Int, Void>>
        array = arrayOfNulls<AddressableHeap.Handle<*, *>>(1000)
        for (i in 0..999) {
            array[i] = h.insert(i)
        }*/

        val array = createArray(1000,h)

        for (i in 0..999) {
            array[i].decreaseKey(array[i].key + 2000)
        }

        for (i in 999 downTo 0) {
            assertEquals(i + 2000, h.deleteMin().key)
        }
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIncreaseKey() {
        val h = createHeap()

        /*val array: Array<AddressableHeap.Handle<Int?, Void>>
        array = arrayOfNulls<AddressableHeap.Handle<*, *>>(15)
        for (i in 0..14) {
            array[i] = h.insert(i + 100)
        }*/

        val array = createArray1(15,h){100 + it}

        assertEquals(100, h.findMin().key)
        array[5].decreaseKey(5)
        assertEquals(5, h.findMin().key)
        array[1].decreaseKey(102)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testIncreaseKeyWithComparator() {
        val h = createHeap(comparator)
        h.insert(10).decreaseKey(9)
    }

    @Test
    @Throws(IOException::class, ClassNotFoundException::class)
    fun testSerializable() {
        var h = createHeap()

        for (i in 0..14) {
            h.insert(i)
        }

        // write
        val baos = ByteArrayOutputStream()
        val oos = ObjectOutputStream(baos)
        oos.writeObject(h)
        oos.close()
        val data = baos.toByteArray()

        // read
        val ois = ObjectInputStream(ByteArrayInputStream(data))
        val o = ois.readObject()
        ois.close()
        h = o as AddressableHeap<Int, Void>

        for (i in 0..14) {
            Assert.assertEquals((15 - i).toLong(), h.size())
            assertEquals(i, h.findMin().key)
            h.deleteMin()
        }
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    fun testSameKey() {
        val h = createHeap()

        Assert.assertTrue(h.isEmpty)

        val handle = h.insert(780)
        handle.decreaseKey(780)
        assertEquals(780, h.deleteMin().key)
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    fun testGetValue() {
        val h = createHeapWithStringValues()

        Assert.assertTrue(h.isEmpty)

        val handle = h.insert(1, "1")
        assertEquals("1", handle.value)
    }

    @Test
    open fun testComparator() {
        val h = createHeap(comparator)

        var i = 0
        while (i < SIZE) {
            h.insert(i)
            assertEquals(i, h.findMin().key)
            Assert.assertFalse(h.isEmpty)
            Assert.assertEquals(h.size(), (i + 1).toLong())
            i++
        }

        i = SIZE - 1
        while (i >= 0) {
            assertEquals(h.findMin().key, i)
            h.deleteMin()
            i--
        }
    }

    @Test
    fun testDecreaseSame() {
        val h = createHeap(comparator)
        h.insert(10).decreaseKey(10)
        assertEquals(10, h.findMin().key)
    }

    @Test(expected = IllegalArgumentException::class)
    fun testInvalidHandleDecreaseKey() {
        val h = createHeap(comparator)
        val handle = h.insert(10)
        h.deleteMin()
        handle.decreaseKey(11)
    }

    @Test
    @Throws(IOException::class, ClassNotFoundException::class)
    fun testSerializableWithComparator() {
        var h = createHeap(comparator)

        for (i in 0..14) {
            h.insert(i)
        }

        // write
        val baos = ByteArrayOutputStream()
        val oos = ObjectOutputStream(baos)
        oos.writeObject(h)
        oos.close()
        val data = baos.toByteArray()

        // read
        val ois = ObjectInputStream(ByteArrayInputStream(data))
        val o = ois.readObject()
        ois.close()
        h = o as AddressableHeap<Int, Void>

        for (i in 0..14) {
            Assert.assertEquals((15 - i).toLong(), h.size())
            assertEquals(15 - i - 1, h.findMin().key)
            h.deleteMin()
        }
        Assert.assertTrue(h.isEmpty)
    }

    @Test
    fun testGetComparator() {
        val h = createHeap(comparator)
        Assert.assertEquals(comparator, h.comparator())
    }

    companion object {

       const val SIZE: Int = 100000

        @JvmStatic
        protected var comparator: Comparator<Int?>? = null

        @JvmStatic
        @BeforeClass
        fun setUpClass(): Unit {
            comparator = TestComparator()
        }
    }
}
